package seqlist.leetcode;

/**
 * 回文链表
 * @author yuisama
 * @date 2022/04/22 21:25
 **/
public class Num234_PalindromeLink {
//    // 1.链表的反转。
//    public ListNode reverseList(ListNode head) {
//        ListNode dummyHead = new ListNode();
//        // 边遍历原链表，边新建节点头插入新链表
//        while (head != null) {
//            ListNode node = new ListNode(head.val);
//            node.next = dummyHead.next;
//            dummyHead.next = node;
//            head = head.next;
//        }
//        return dummyHead.next;
//    }
//
//    /**
//     * 判断一个链表是否是回文链表
//     * @param head
//     * @return
//     */
//    public boolean isPalindrome(ListNode head) {
//        ListNode newLink = reverseList(head);
//        while (head != null) {
//            if (head.val != newLink.val) {
//                return false;
//            }
//            head = head.next;
//            newLink = newLink.next;
//        }
//        return true;
//    }

    public boolean isPalindrome(ListNode head) {
        ListNode middleLink = middleNode(head);
        ListNode l2 = reverse(middleLink);
        while (l2 != null) {
            if (head.val != l2.val) {
                return false;
            }
            head = head.next;
            l2 = l2.next;
        }
        return true;
    }

    public ListNode middleNode(ListNode head) {
        ListNode fir = head,sec = head;
        while (fir != null && fir.next != null) {
            fir = fir.next.next;
            sec = sec.next;
        }
        return sec;
    }


    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode node = head.next;
        ListNode newHead = reverse(head.next);
        node.next = head;
        head.next = null;
        return newHead;
    }
}